package com.LeetCode.BFS;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 油漆填充工具
 */
public class floodFill {

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int n = image.length;
        int m = image[0].length;
        int pre = image[sr][sc];
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.add(new int[]{sr,sc});
        int[] des = {-1,0,1,0,-1};
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            int nx = cur[0];
            int ny = cur[1];
            image[nx][ny] = newColor;
            for(int i = 0; i<4; i++){
                nx = cur[0];
                ny = cur[1];
                nx += des[i];
                ny += des[i+1];
                if(nx >= 0 && nx < n && ny >= 0
                        && ny < m && !visited[nx][ny] && image[nx][ny] == pre){

                    queue.add(new int[]{nx,ny});
                    visited[nx][ny] = true;
                }
            }
        }
        return image;
    }

    int n , m, oldColor, newColor;

    public int[][] floodFill2(int[][] image, int sr, int sc, int newColor){
        this.n = image.length;
        this.m = image[0].length;
        this.oldColor = image[sr][sc];
        this.newColor = newColor;
        dfs(image, sr, sc);
        return image;
    }

    public void dfs(int[][] image, int i, int j){
        if(i < 0 || i >= n || j < 0 || j >= m || image[i][j] != oldColor || image[i][j] == newColor)
            return;

        image[i][j] = newColor;

        dfs(image, i+1, j);
        dfs(image, i-1, j);
        dfs(image, i, j+1);
        dfs(image, i, j-1);
    }

    @Test
    public void test(){
        int[][] image1 = {
                {1,1,1},
                {1,1,0},
                {1,0,1}
        };

        int[][] image2 = {
                {0,0,0},
                {0,1,0}
        };

        for(int[] arr : floodFill2(image2, 1,1,2)){
            for(int num : arr){
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}
